home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / List / List.h < prev    next >
C/C++ Source or Header  |  1992-06-29  |  20KB  |  530 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MJF 03/27/89 -- Initial design and implementation.
  13. // Updated: MJF 04/15/89 -- Added a Base List class.
  14. // Updated: MJF 06/01/89 -- Added const to member function arguments.
  15. // Updated: MJF 06/21/89 -- Changed return types from List& to void or Boolean.
  16. // Updated: MJF 08/10/89 -- Changed return values of methods to List reference
  17. // Updated: MBN 08/20/89 -- Changed template usage to reflect new syntax
  18. // Updated: LGO 10/02/89 -- Fix reference count bug in insert_after_node
  19. // Updated: LGO 10/02/89 -- Set reference count to 1 in node constructor and
  20. //                          eliminate many reference method calls.
  21. // Updated: MBN 10/11/89 -- Change "current_position" to "curpos" and also
  22. //                          "previous_position" to "prevpos"
  23. // Updated: LGO 10/18/89 -- Get rid of the sort_test method
  24. // Updated: LGO 10/18/89 -- Simplify the value method to avoid yacc stack oflow
  25. // Updated: MBN 10/19/89 -- Added optional argument to set_compare method
  26. // Updated: MBN 10/19/89 -- Added optional starting position to find method
  27. // Updated: MBN 02/14/90 -- Make push return FALSE if out of heap memory
  28. // Updated: VDN 02/21/92 -- New lite version and plug all memory leaks
  29. //
  30. // A list is simply  made up  of a  collection of nodes.   Each node contains a
  31. // reference count, a  pointer to  the next node  in  the  list, and the   data
  32. // object.  An overview of the structure of  the  List class, along with  a
  33. // synopsis of each member and friend function, can be found in the Base_List.h
  34. // header file.
  35. //
  36. //
  37. //                      +--------+         +--------+         +--------+
  38. //                      | Ref=2  |         | Ref=1  |         | Ref=2  |
  39. //    +---------+       +--------+         +--------+         +--------+
  40. //    |  List --+-+---->| Next --+-------->| Next --+----+--->| Next 0 |
  41. //    +---------+ |     +--------+         +--------+    |    +--------+
  42. //                |     | Data   |         | Data   |    |    | Data   |
  43. //                |     +--------+         +--------+    |    +--------+
  44. //                |                                      |
  45. //    +---------+ |                          +---------+ |
  46. //    |  List --+-+                          |  List --+-+
  47. //    +---------+                            +---------+
  48. //
  49.  
  50. #ifndef LISTH                    // If LIST not yet defined,
  51. #define LISTH                    // indicate class List done
  52.  
  53. #ifndef STDARGH
  54. #if defined(DOS)
  55. extern "C" {
  56. #include <stdarg.h>                // for variable arglists
  57. }
  58. #else
  59. #include <stdarg.h>                // for varialbe arglists
  60. #endif
  61. #define STDARGH
  62. #endif
  63.  
  64. #ifndef BASE_LISTH                // If Base LIST not defined,
  65. #include <cool/Base_List.h>            // include Base_List header
  66. #endif
  67.  
  68.  
  69. template <class Type> 
  70. class CoolList_Node<Type> : public CoolList_Node {
  71. friend class CoolList<Type>;
  72. public:
  73.   CoolList_Node<Type>(CoolList_Node<Type>&);    // Copy constructor
  74.   CoolList_Node<Type>(const Type& head, CoolList_Node<Type>* tail);
  75.   virtual void* get_data();            // Returns data element 
  76.   virtual void  set_data(void*);        // Set data element
  77.  
  78. protected:
  79.   Type data;                    // Data of node
  80.   virtual ~CoolList_Node<Type>();        // Destructor is virtual
  81. };
  82.  
  83. template <class Type> CoolList {
  84.   typedef Boolean (*Type##_CoolList_Compare)(const Type&, const Type&);    // Compare function
  85.   typedef Boolean (*Type##_CoolList_Predicate)(const Type&, const Type&); // Predicate function
  86.  
  87.   DECLARE CoolList_Node<Type>;            // Generate header file
  88. }
  89.  
  90. template <class Type>
  91. class CoolList<Type> : public CoolList {
  92. public:
  93.   CoolList<Type>();                // List<int> l;  a nil list.
  94.   CoolList<Type>(int n, Type head, ...);    // List<int> l4 = (3,11,22,33);
  95.   CoolList<Type>(const Type& head);        // List<String> l1 = "333";
  96.   CoolList<Type>(const Type& head, CoolList<Type>& tail); //List<String>l2 = ("a", l1);
  97.   CoolList<Type>(CoolList<Type>& tail);              // Copy constructor
  98.  
  99.   virtual ~CoolList<Type>();            // Destructor is virtual
  100.   
  101.   inline Type& value();                // Value at current position
  102.   int position();                // Current position index
  103.   
  104.   void set_compare(Type##_CoolList_Compare cf = NULL); // Sets Compare
  105.   inline CoolList<Type>& operator=(const CoolList<Type>& l);  // list1 = list2;
  106.   
  107.   Type& operator[](int n);            // x = l[n];
  108.   inline Type& get(int n = 0);            // Returns nth data-node
  109.   Boolean put(const Type& x, int n = 0);    // Sets nth data-node to x
  110.   
  111.   inline int position(const Type& x);        // Returns zero-relative index 
  112.   inline CoolList_state& current_position ();    // Set/Get current position
  113.   inline Boolean find(const Type& x, CoolList_state s = NULL); // True if contains x
  114.   
  115.   // returns true if THIS list contains element x and 
  116.   // sets list l to a sublist in THIS list starting at first occurrence of x
  117.   inline Boolean member(CoolList<Type>& l, const Type& x);
  118.   
  119.   Boolean push(const Type& x);            // Adds x to head of this list
  120.   inline Boolean push_new(const Type& x);    // Push if not already member
  121.   inline Boolean push_end(const Type& x);    // Adds x at end of this list
  122.   inline Boolean push_end_new(const Type& x);    // Push_end(x) if not member
  123.   
  124.   Boolean pop(Type& result);            // Removes head/returns data
  125.   Type pop();                    // Removes head/returns data
  126.   
  127.   Type remove();                // Remove/return curpos
  128.   inline Boolean remove(const Type& x);        // Removes first occurrence
  129.   
  130.   inline Boolean replace(const Type& old_data, const Type& new_data); 
  131.   inline Boolean replace_all(const Type& old_data, const Type& new_data); 
  132.   
  133.   inline void sort(Type##_CoolList_Predicate f); // Sort list using predicate
  134.   inline void merge(const CoolList<Type>& l, Type##_CoolList_Predicate f); // Merge
  135.   
  136.   inline Boolean insert_before(const Type& new_item); // Insert item before
  137.   inline Boolean insert_after(const Type& new_item);  // Insert item after
  138.   
  139.   inline Boolean insert_before(const Type& new_item, const Type& targ_item);
  140.   inline Boolean insert_after(const Type& new_item, const Type& targ_item);
  141.   
  142.   inline CoolList<Type>& operator&=(const CoolList<Type>& l); // Intersection/assign
  143.   inline CoolList<Type>& operator|=(const CoolList<Type>& l); // Union/assign
  144.   inline CoolList<Type>& operator-=(const CoolList<Type>& l); // Difference/assign
  145.   inline CoolList<Type>& operator^=(const CoolList<Type>& l); // XOR/assign
  146.   inline CoolList<Type>& operator+=(const CoolList<Type>& l); // Concatenation/assign
  147.   
  148.   inline CoolList<Type> operator&(const CoolList<Type>& l); // Intersection
  149.   inline CoolList<Type> operator|(const CoolList<Type>& l); // Union
  150.   inline CoolList<Type> operator-(const CoolList<Type>& l); // Difference
  151.   inline CoolList<Type> operator^(const CoolList<Type>& l); // XOR
  152.   inline CoolList<Type> operator+(const CoolList<Type>& l); // Concatenation
  153.  
  154. private:
  155.   static Type##_CoolList_Compare compare_s;    // Function used by == test
  156.   friend Boolean Type##_CoolList_is_data_equal(const Type& a, const Type& b); // a==b
  157.   
  158.   CoolList<Type>(CoolList_Node<Type>*);        // Internal-use constructor
  159.   virtual CoolList* new_list(CoolList_Node*);    // Creates a new list from node
  160.   
  161.   virtual CoolList_Node* insert_before_node(void* v, CoolList_Node* next_np);
  162.   virtual CoolList_Node* insert_after_node(void* v, CoolList_Node* prev_np) const;
  163.   
  164.   virtual Boolean compare_data(const void*, const void*) const;
  165.   virtual Boolean do_find(CoolList_Node* np, const void* x,
  166.               CoolList_Node*& cp, CoolList_Node*& pp) const;
  167.   
  168.   virtual void output_data(ostream&, const CoolList_Node*) const;
  169. };
  170.  
  171.  
  172. // value() -- Returns value at current position.
  173. // Input:     None.
  174. // Output:    A Type reference of data at current position.
  175.  
  176. template <class Type> 
  177. inline Type& CoolList<Type>::value() {
  178. #ifdef ERROR_CHECKING  
  179.   if (CoolList::curpos == NULL)
  180.     this->value_error (#Type);            // Raise exception
  181. #endif
  182.   return ((CoolList_Node<Type>*) CoolList::curpos)->data;
  183. }
  184.  
  185. // position -- Return current position.
  186. // Input:      THIS.
  187. // Output:     An integer representing current position.
  188.  
  189. template <class Type> 
  190. inline int CoolList<Type>::position() {
  191.   return CoolList::position();            // can inherit only if has
  192. }
  193.  
  194.  
  195. // operator=() -- Assigns THIS to the specified list.
  196. // Input:         A reference to a list which THIS will be assigned to.
  197. // Output:        A reference to THIS.
  198.  
  199. template <class Type> 
  200. inline CoolList<Type>& CoolList<Type>::operator=(const CoolList<Type>& l) {
  201.   if (this != &l) 
  202.     CoolList::operator=(l);
  203.   return *this;
  204. }
  205.  
  206.  
  207. // get() -- Returns the nth node of THIS. With no arguments, returns first node
  208. // Input:   A positive integer index (default 0).
  209. // Output:  A Type reference of data in the nth node of THIS.
  210.  
  211. template <class Type> 
  212. inline Type& CoolList<Type>::get(int n) {
  213. #if ERROR_CHECKING
  214.   if (n < 0)
  215.     this->get_error (#Type, n);
  216. #endif
  217.   return operator[](n);
  218. }
  219.  
  220.  
  221.  
  222. // position() -- Returns the position of the specified data item in this list.
  223. //               If item not in list, returns -1
  224. // Input:        A Type reference to a data item.
  225. // Output:       The integer position.
  226.  
  227. template <class Type> 
  228. inline int CoolList<Type>::position(const Type& x) {
  229.   return CoolList::position((const void*)&x);
  230. }
  231.  
  232. // current_position () -- Return current position state
  233. // Input:                 None
  234. // Output:                Reference to current position state
  235.  
  236. template <class Type> 
  237. inline CoolList_state& CoolList<Type>::current_position () {
  238.   return this->curpos;
  239. }
  240.  
  241.  
  242. // find() -- Returns TRUE if the specified element is a member of THIS list.
  243. // Input:    A Type reference to data item to be searched.
  244. // Output:   TRUE or FALSE.
  245.  
  246. template <class Type> 
  247. inline Boolean CoolList<Type>::find(const Type& x, CoolList_state s) {
  248.   if (s == NULL)                // If no starting position?
  249.     s = this->node_ptr;                // Start at head of list
  250.   return this->do_find(s, &x, this->curpos, this->prevpos); // Find and return
  251. }
  252.  
  253.  
  254. // member() -- Returns the tail of THIS list beginning with the first
  255. //             occurrence of the specified data item.
  256. // Input:      A Type reference to data item to be searched.
  257. // Output:     A list reference of some tail of THIS.
  258.  
  259. template <class Type> 
  260. inline Boolean CoolList<Type>::member(CoolList<Type>& l, const Type& x) {
  261.   return CoolList::member(l, (const void*)&x);
  262. }
  263.  
  264.  
  265.  
  266. // push_new() -- Pushes the specified data item at front of this list if it is
  267. //               not already a member 
  268. // Input:        A reference to a new Type.
  269.   // Output:       TRUE if item not on list, FALSE otherwise.
  270.  
  271. template <class Type> 
  272. inline Boolean CoolList<Type>::push_new(const Type& x) {
  273.   return CoolList::push_new((const void*)&x);
  274. }
  275.  
  276.  
  277. // push_end() -- Appends the specified data item to the end of this list
  278. // Input:        A Type reference to the data item to be appended.
  279. // Output:       TRUE.
  280.  
  281. template <class Type> 
  282. inline Boolean CoolList<Type>::push_end(const Type& x) {
  283.   return CoolList::push_end((const void*)&x);
  284. }
  285.  
  286.  
  287. // push_end_new() -- Appends the specified data item to the end of THIS list
  288. //                   if not already a member 
  289. // Input:            A Type reference to the data item to be appended.
  290. // Output:           TRUE if item not on list, FALSE otherwise.
  291.  
  292. template <class Type> 
  293. inline Boolean CoolList<Type>::push_end_new(const Type& x) {
  294.   return CoolList::push_end_new((const void*)&x);
  295. }
  296.  
  297.  
  298. // remove() -- Removes the first occurrence of the specified item in this list
  299. // Input:      A refernce to data item to be removed.
  300. // Output:     TRUE if item found and removed, FALSE otherwise.
  301.  
  302. template <class Type> 
  303. inline Boolean CoolList<Type>::remove(const Type& x) {
  304.   return CoolList::remove((const void*)&x);
  305. }
  306.  
  307.  
  308. // replace() -- Replaces the first occurrence of specified data item in THIS
  309. //              list with a new value
  310. // Input:       A reference to the data item to be replaced and the new value.
  311. // Output:      TRUE if item found and replaced, FALSE otherwise.
  312.  
  313. template <class Type> 
  314. inline Boolean CoolList<Type>::replace(const Type& old_data, const Type& new_data) {
  315.   return CoolList::replace((const void*)&old_data, (const void*)&new_data);
  316. }
  317.  
  318.  
  319. // replace_all() -- Replaces all occurrences of the specified data item in THIS
  320. //                  list with a new value.
  321. // Input:           A reference to the data item to be replaced and new value.
  322. // Output:          TRUE if at least one item found and replaced, else FALSE
  323.  
  324. template <class Type> 
  325. inline Boolean CoolList<Type>::replace_all(const Type& old_d, const Type& new_d) {
  326.   return CoolList::replace_all((const void*)&old_d, (const void*)&new_d);
  327. }
  328.  
  329.  
  330. // sort() -- Sorts the elements of THIS using the specified predicate function.
  331. // Input:    A predicate function pointer.
  332. // Output:   None.
  333.  
  334. template <class Type> 
  335. inline void CoolList<Type>::sort(Type##_CoolList_Predicate f) {
  336.   CoolList::sort((Predicate)f);
  337. }
  338.  
  339.  
  340. // merge() -- Merges the elements of list with the elements of the specified
  341. //            list sorted with the specified predicate function
  342. // Input:     A reference to a list to be merged and a predicate function
  343. //            pointer.
  344. // Output:    None.
  345.  
  346. template <class Type> 
  347. inline void CoolList<Type>::merge(const CoolList<Type>& l, Type##_CoolList_Predicate f) {
  348.   CoolList::merge(l, (Predicate)f);
  349. }
  350.  
  351.  
  352. // insert_before() -- Inserts the specified item before the current position
  353. // Input:             A Type reference of new item.
  354. // Output:            TRUE if current position is valid, FALSE otherwise.
  355.  
  356. template <class Type> 
  357. inline Boolean CoolList<Type>::insert_before(const Type& new_item) {
  358. #if ERROR_CHECKING
  359.   if (this->curpos == NULL)
  360.     this->before_error (#Type);
  361. #endif
  362.   return CoolList::insert_before((const void*)&new_item);
  363. }
  364.  
  365.  
  366. // insert_after() -- Inserts the specified item after the current position
  367. // Input:            A Type reference of new item.
  368. // Output:           TRUE if current position is valid, FALSE otherwise.
  369.  
  370. template <class Type> 
  371. inline Boolean CoolList<Type>::insert_after(const Type& new_item) {
  372. #if ERROR_CHECKING
  373.   if (this->curpos == NULL)
  374.     this->after_error (#Type);
  375. #endif
  376.   return CoolList::insert_after((const void*)&new_item);
  377. }
  378.  
  379.  
  380. // insert_before() -- Inserts the specified new item before the specified
  381. //                    target item in this list
  382. // Input:             Two data Type references.
  383. // Output:            TRUE if target item found, FALSE otherwise.
  384.  
  385. template <class Type> 
  386. inline Boolean CoolList<Type>::insert_before(const Type& new_item,
  387.                      const Type& target_item) {
  388.   return CoolList::insert_before((const void*)&new_item,(const void*)&target_item);
  389. }
  390.  
  391. // Boolean insert_after(Type&, Type&) -- inserts the specified new item
  392. //                                       after the specified target item
  393. //                                       in THIS list.
  394. //
  395. // Input:   Two data Type references.
  396. // Output:  TRUE if target item found, FALSE otherwise.
  397.  
  398. template <class Type> 
  399. inline Boolean CoolList<Type>::insert_after(const Type& item, const Type& target) {
  400.   return CoolList::insert_after((const void*)&item, (const void*)&target);
  401. }
  402.  
  403.  
  404. // operator&=() -- Intersection of THIS list with the specified list.
  405. // Input:          A reference to the list.
  406. // Output:         A modified THIS.
  407.  
  408. template <class Type> 
  409. inline CoolList<Type>& CoolList<Type>::operator&=(const CoolList<Type>& l) {
  410.   this->set_intersection(l);
  411.   return *this;
  412. }
  413.  
  414.  
  415. // operator|=() -- Union of THIS list with the specified list.
  416. // Input:          A reference to the list.
  417. // Output:         A reference to a new list containing a copy of the elements
  418. //                 of THIS list and the elements of the specified list.
  419.  
  420. template <class Type> 
  421. inline CoolList<Type>& CoolList<Type>::operator|=(const CoolList<Type>& l) {
  422.   this->set_union(l);
  423.   return *this;
  424. }
  425.  
  426.  
  427. // operator-=() -- Difference of THIS list with the specified list.
  428. // Input:          A reference to the list.
  429. // Output:         A modified THIS.
  430.  
  431. template <class Type> 
  432. inline CoolList<Type>& CoolList<Type>::operator-=(const CoolList<Type>& l) {
  433.   this->set_difference(l);
  434.   return *this;
  435. }
  436.  
  437.  
  438. // operator^=() -- Exclusive-or of THIS list with the specified list.
  439. // Input:          A reference to the list.
  440. // Output:         A modified THIS.
  441.  
  442. template <class Type> 
  443. inline CoolList<Type>& CoolList<Type>::operator^=(const CoolList<Type>& l) {
  444.   this->set_xor(l);
  445.   return *this;
  446. }
  447.  
  448.  
  449. // operator+=() -- Concatenates THIS list with the specified list.
  450. // Input:          A reference to the list to be concatenated.
  451. // Output:         A modified THIS.
  452. //
  453.  
  454. template <class Type> 
  455. inline CoolList<Type>& CoolList<Type>::operator+=(const CoolList<Type>& l) {
  456.   this->append(l);
  457.   return *this;
  458. }
  459.  
  460. // operator&() -- Intersection of a copy of THIS list with the specified list
  461. // Input:         A reference to the list.
  462. // Output:        A new list ret. by value containing a copy of the elements
  463. //                of THIS and the elements of the specified list.
  464.  
  465. template <class Type> 
  466. inline CoolList<Type> CoolList<Type>::operator&(const CoolList<Type>& l) {
  467.   CoolList<Type> new_copy;            // temporary deleted on exit
  468.   new_copy.copy(*this);                // copy nodes of this 
  469.   new_copy.set_intersection(l);            // mutate with inters. of l
  470.   return new_copy;                // will copy only list header
  471. }
  472.  
  473.  
  474. // operator|() -- Union of a copy of THIS list with the specified list
  475. // Input:         A reference to the list.
  476. // Output:        A reference to a new list containing a copy of the elements
  477. //                of THIS and the elements of the specified list.
  478.  
  479. template <class Type> 
  480. inline CoolList<Type> CoolList<Type>::operator|(const CoolList<Type>& l) {
  481.   CoolList<Type> new_copy;            // temporary deleted on exit
  482.   new_copy.copy(*this);                // copy nodes of this
  483.   new_copy.set_union(l);            // mutate with union of l
  484.   return new_copy;                // will copy only list header
  485. }
  486.  
  487.  
  488. // operator-() -- Difference of a copy of THIS list with the specified list.
  489. // Input:         A reference to the list.
  490. // Output:        A reference to a new list containing a copy of the elements
  491. //                of THIS and the elements of the specified list.
  492.  
  493. template <class Type> 
  494. inline CoolList<Type> CoolList<Type>::operator-(const CoolList<Type>& l) {
  495.   CoolList<Type> new_copy;            // temporary deleted on exit
  496.   new_copy.copy(*this);                // copy nodes of this 
  497.   new_copy.set_difference(l);            // mutate with diff of l
  498.   return new_copy;                // will copy only list header
  499. }
  500.  
  501.  
  502. // operator^() -- Exclusive-or of a copy of THIS list with the specified list.
  503. // Input:         A reference to the list.
  504. // Output:        A reference to a new list containing a copy of the elements
  505. //                of THIS and the elements of the specified list.
  506.  
  507. template <class Type> 
  508. inline CoolList<Type> CoolList<Type>::operator^(const CoolList<Type>& l) {
  509.   CoolList<Type> new_copy;            // temporary deleted on exit
  510.   new_copy.copy(*this);                // copy nodes of this
  511.   new_copy.set_xor(l);                // mutate with xor of l
  512.   return new_copy;                // will copy only list header
  513. }
  514.  
  515.  
  516. // operator+() -- Concatenates a copy of THIS list with the specified list.
  517. // Input:         A reference to the list to be concatenated.
  518. // Output:        A reference to a new list containing a copy of the elements
  519. //                of THIS and the elements of the specified list.
  520.  
  521. template <class Type> 
  522. inline CoolList<Type> CoolList<Type>::operator+(const CoolList<Type>& l) {
  523.   CoolList<Type> new_copy;            // temporary deleted on exit
  524.   new_copy.copy(*this);                // copy nodes of this 
  525.   new_copy.append(l);                // mutate with concat. of l
  526.   return new_copy;                // will copy only list header
  527. }
  528.  
  529. #endif                // End #ifdef of LISTH
  530.